package com.example.leetcode.leetcode;

/**
 * @author zht
 * @date 2021/1/12 10:16
 */
public class Solution79 {
    public static boolean exist(char[][] board, String word) {
        char [] charArray = word.toCharArray();
        for (int i = 0; i < board.length; i++) {
            for (int j = 0; j < board[0].length; j++) {
                if (dfs(i,j,charArray,board,0)){
                    return true;
                }
            }
        }
        return false;
    }
    /** 深度优先遍历 递归实现回溯*/
    public static boolean dfs(int i, int j, char [] charArray, char [][]board,int index){
        // 判断特殊情况
        if (i>=board.length || i<0 || j >=board[0].length || j<0||charArray[index] != board[i][j]){
            return false;
        }
        // 完成
        if (index== charArray.length-1){
            return true;
        }
        // 标记,避免递归过程中搜过走过的路径
        char temp = board[i][j];
        board[i][j] = '.';
        // 递归
        boolean res =
                dfs(i-1,j,charArray,board,index+1)||
                dfs(i+1,j,charArray,board,index+1)||
                dfs(i,j-1,charArray,board,index+1)||
                dfs(i,j+1,charArray,board,index+1);
        // 复原
        board[i][j]= temp;
        return res;
    }
    public static void main(String[] args) {

    }
}
